package leetcode.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution39 {

    public static void main(String[] args) {
        Solution39 s = new Solution39();
        int[] candidates = {2,7,6,3,5,1};
        int target = 9;
        List<List<Integer>> lists = s.combinationSum(candidates, target);
        for (List<Integer> list: lists) {
            System.out.println(list);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        ArrayList<Integer> cur = new ArrayList<>();
        backTracking(candidates,target,res,cur,0);
        return (List) res;
    }

//    public void backTracking(int[] candidates, int target, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, int curIdx){
//        if(target<0) return;
//        if(target==0){
//            res.add((ArrayList<Integer>)cur.clone());
//        }
//        for (int i = curIdx; i < candidates.length; i++) {
//            cur.add(candidates[i]);
//            backTracking(candidates,target-candidates[i],res,cur,i);
//            cur.remove(cur.size()-1);
//        }
//    }
    public boolean backTracking(int[] candidates, int target, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> cur, int curIdx){
        if(target<0) return false;
        if(target==0){
            res.add((ArrayList<Integer>)cur.clone());
            return false;
        }
        for (int i = curIdx; i < candidates.length; i++) {
            cur.add(candidates[i]);
            boolean continueLoop = backTracking(candidates,target-candidates[i],res,cur,i);
            cur.remove(cur.size()-1);
            if(!continueLoop) break;
        }
        return true;
    }
}
